class Solution {
public:
    bool find( TreeNode* sub,TreeNode* x )
    {
         if( sub == nullptr )
         {
             return false;
         }
         return ( sub == x ) || find( sub->left,x) || find( sub->right,x);
        
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if( root == nullptr )
        {
            return nullptr;
        }
        if( root == p || root == q )
        {
            return root;
        }
        bool pInLeft,pInRight,qInLeft,qInRight;
        pInLeft = find( root->left,p);
        pInRight = !pInLeft;
        
        qInLeft = find( root->left,q);
        qInRight = !qInLeft;

        if( pInLeft && qInRight || pInRight && qInLeft )
        {
            return root;
        }     
        else if ( pInLeft && qInLeft )
        {
            return  lowestCommonAncestor(root->left,p,q);
        }
        else if ( pInRight && qInRight )
        {
            return  lowestCommonAncestor(root->right,p,q);
        }
        else{
            return nullptr;
        }
    }
};